\section{Nash equilibria}
\label{sec:game.nash}

\subsection{The local infection model: $d = 1$}
For the local infection model, we show that a pure NE always
exists.  Our proof is by a reduction to a result of Borodin et
al. \cite{Borodin00} on existence of subgraphs with restricted degree
sequences; their result is based on a potential function argument. 
%Let $N(v)$ denote the set of neighbors of $v$ in $\CG$.
\junk{
When $d = 1$, the probability $p_v(\vec{a})$ that a node $v$ gets
attacked given strategy vector $\vec{a}$ equals $w(N(v))+w(v)$, where
$N(v)$ is the set consisting of the neighbors of $v$ in \attack.
}

\newcommand{\degset}[2]{\mbox{deg}_{#1}(#2)}

\begin{theorem}
Every $\GNS{1}$ instance has a pure NE.
\end{theorem}
\begin{proof}
We first define two functions $a:V\rightarrow \mathbb{R}$ and
$b:V\rightarrow \mathbb{R}$. For each $v\in V$, $a(v)=
w(N(v))-\frac{C_v}{L_v}+w(v)$ and $b(v)=\frac{C_v}{L_v}-w(v)$.  We argue
next, using a generalization of an argument due to~\cite{Borodin00},
that there exists a partition $V=A\cup B$ such that for each $v\in A$,
we have $w(A \cap N(v)) \leq a(v)$ and for each $v\in B$, we have $w(B
\cap N(v)) \leq b(v)$.  Consider the following function that defines a
potential for each partition $(A,B)$.
\begin{eqnarray*}
R(A,B) = & \sum_{v\in A} w(v)\left(w(A \cap N(v)) - 2a(v)\right)\\
& + \sum_{v\in B} w(v)\left(w(B \cap N(v))-2b(v)\right)
\end{eqnarray*}
Among all the partitions, we take a partition $(A^*, B^*)$
minimizing $R$ and assert that $(A^*, B^*)$ is the partition we
need. Suppose that a vertex $x$ belongs to $A^*$, and $w(A^* \cap N(x))
>a(x)$. Now we move $x$ from $A^*$ to $B^*$ to obtain the partition
$(A'=A^*\setminus\{x\},B'=B^*\cup\{x\})$.  Because $a(x)+b(x)\ge w(N(x))$, we have $w(N(x) \cap B^*) \le b(x)$. 
It is easy to verify that $R(A^*,B^*)-R(A',B')$ equals
\begin{eqnarray*}
& & w(x)\left(w(N(x) \cap A^*) -2a(x)\right)+w(x)w(N(x) \cap A^*) - \\
& & \quad \quad w(x)\left(w(N(x) \cap B^*) -2b(x)\right)- w(x)w(N(x) \cap B^*) \\
&=&
2w(x)\left(w(N(x) \cap A^*)-a(x)\right) - 2w(x)\left(w(N(x) \cap B^*)-b(x)\right) >0
\end{eqnarray*}.
\iffalse
By setting $A'$ to be $A^* - \{x\}$, $R$ decreases by
$w(x)\left(w(N(x) \cap A^*) -2a(x)\right)+w(x)w(N(x) \cap A^*)= 2w(x)\left(w(N(x) \cap
A^*)-a(x)\right)$, which is a positive value. By setting $B'$ to be
$B^* + \{x\}$, $R$ increases by $w(x)\left(w(N(x) \cap B^*) -2b(x)\right)+ w(x)w(N(x) \cap
B^*) =2w(x)\left(w(N(x) \cap B^*)-b(x)\right)$, which is a negative value
or 0. 
\fi
This means $R(A^*,B^*)>R(A',B')$, which is a contradiction. A similar inequality
follows if there is a vertex $x\in B^*$ with $w(B^*\cap N(x))>b(x)$. Therefore,
such a vertex $x$ doesn't exist implying that $(A^*,B^*)$ is the
desired partition.

Given such a partition $(A,B)$, we establish the existence of pure NE.
Let $\vec{a}$ be a strategy vector with $a_v=1$ for all $v\in A$ and
$a_v=0$ for all $v\in B$; i.e., $A$ denotes the set of secure
nodes. Then, we argue that $\vec{a}$ is indeed a pure NE. First consider the case where $v\in A$. Then $v$ is secure and pays cost $C_v$. If $v$ changes strategy, its expected infection cost is $L_v\left(w(N(v)\cap B) + w(v)\right)$. Since $v\in A$, we have $w(N(v)\cap A) \le a(v) = w(N(v)) - C_v/L_v + w(v)$. Therefore, $C_v \le L_v\left(w(N(v)\cap B) + w(v)\right)$, i.e. $v$ won't change its strategy. Next consider $v\in B$. Then $v$ is not secure and its expected infection cost is $L_v\left(w(N(v)\cap B) + w(v)\right)$. If $v$ changes strategy, its cost is $C_v$. Since $v\in B$, we have $w(N(v)\cap B) \le b(v) = C_v/L_v - w(v)$. Therefore, $L_v\left(w(N(v)\cap B) + w(v)\right) \le C_v$, i.e. $v$ won't change its strategy. Thus it follows that $\vec{a}$ is a Nash equilibrium.

\junk{, using Lemma
\ref{lemma:game.nechar}.  First consider the case where $v\in A$.  Then $v$
is secure, and $w(N(v) \cap A)$ denotes the sum of its infection
probability and the sum, over its neighbors, of their infection
probabilities, for this strategy vector. Since $w(N(v) \cap A) \leq
w(N(v)) - C_v/L_v + w(v)$, the expected number of insecure neighbors
of $v$ that get infected is at least $C_v/L_v - w(v)$.  Next, suppose
$v\in B$, i.e., it is not secure in $\vec{a}$. Since $w(N(v) \cap B)
\leq C_v/N_v-1$, the number of insecure neighbors is at most $C_v/N_v
- w(v)$. Therefore, by Lemma \ref{lemma:game.nechar}, it follows that
$\vec{a}$ is a Nash equilibrium.}
\end{proof}

When the security and infection costs are uniform, we show that
for the case of $d = 1$, the maximum ratio of the cost of a pure NE to the
social optimum is bounded by the maximum degree.

\begin{lemma}
\label{lemma:game.poa-d1}
When security and infection costs are uniform, and $w_v = 1/n$
$\forall v$, the price of anarchy in \GNS{1} is at most $\Delta + 1$,
where $\Delta$ is the maximum degree of the contact graph.
\end{lemma}
\begin{proof}
Let $C$ and $L$ denote the security and infection costs, respectively.
Suppose $C>L(\Delta+1)/n$. Then no node is secured in any pure NE
and therefore, the cost of any pure NE is at most $L(\Delta+1)$. In
the optimum strategy, each node has a cost of $C$ if it is secured,
or at least $L/n$ otherwise.  Therefore the optimal cost is at least
$L$, and the lemma follows in this case.

Next, consider the case $C\leq L(\Delta+1)/n$. In any pure NE, any node has cost at most $C$, and
therefore the cost of a pure NE is at most $Cn$. If $C\leq L/n$, the optimum
cost is also $Cn$, and therefore, we assume $C\geq L/n$.
In an optimum
solution, each node has cost at least $L/n$, and therefore, the
optimal cost is at least $L$. Therefore, the price of anarchy in this
case is at most $\Delta+1$.
\end{proof}


\subsection{The global infection model: $d = \infty$}
\junk{ In Aspnes et al's model, vaccination is reliable, i.e. once a
  person is vaccinated, he is immune from the disease. Also the
  disease they considered is highly infectious, which means infected
  nodes will eventually infect all their neighbors who are not
  immune. Each node has all the information (which nodes get
  vaccinated and which are not).  } 

In this section, we consider the global model ($d = \infty$); thus,
any node $v$ is capable of infecting any other node $u$ as long there
is a path of insecure nodes between $v$ and $u$ in the contact graph
$\CG$.  In this special case, our model is a generalization of the
model of~\cite{AspnesCY2006} in that we allow different security
costs, infection costs, and initial infection probabilities.

\begin{theorem}
  Every $\GNS{\infty}$ instance has a pure NE\junk{\footnote{In fact,
      our proof of existence of pure NE even extends to the case where
      the initial infection may originate at multiple attack points
      simultaneously, even in an arbitrarily correlated manner; we
      defer the details to the full paper.}}.
\end{theorem}

\begin{proof}
Let $t_v = C_v/L_v$; we refer to $t_v$ as the
threshold for $v$.  We relabel the $n$ nodes so that $t_1\ge
t_2\ge\dots\ge t_n$, where we break ties arbitrarily.  Given a
strategy vector $\vec{a}$, we say that a secure node $v$ is \textit{happy} if
$w(S_v(\vec{a}[v/0]))>t_v$, and \textit{unhappy} otherwise.  Similarly, an
insecure node $v$ is \textit{happy} if $w(S_v(\vec{a}))\leq t_v$, and \textit{unhappy}
otherwise.  Recall that when $d = \infty$, $S_v(\vec{a})$ is the set
of nodes that can reach $v$ in \attack.

Consider the following potential function.
\[\hat{\Phi}(\vec{a}) = \left(\Phi_{1}(\vec{a}),\Phi_{2}(\vec{a}),\dots,\Phi_{n}(\vec{a})\right)\]
where $\Phi_{v}(\vec{a})$ is $0$ if $v$ is secure, $-1$ if $v$ is
insecure and happy, and $1$ otherwise.  We next show this potential
always lexicographically decreases.  There are two cases:
\begin{enumerate}
\item Some node $v$ switches from being an insecure unhappy node to
  being a secure happy node, changing the strategy vector from
  $\vec{a}$ to $\vec{b}$.  In this case $w(S_v(\vec{a})) > t_v$.
  Since the set of secure nodes in $\vec{b}$ is a superset of the set
  of secure nodes in $\vec{a}$, it follows that for any node $u$,
  $w(S_u(\vec{b})) \le w(S_u(\vec{a}))$; it thus follows that no
  insecure happy node in $\vec{a}$ can become unhappy in $\vec{b}$.
  Therefore, the $v$th component of the potential decreases by $1$,
  while none of the other components increases.
\item Some node $v$ switches from being secure to not being secure,
  changing the strategy vector from $\vec{a}$ to $\vec{b}$.  In this
  case, $w(S_v(\vec{b})) \le t_v$.  We thus have the $v$th component
  of the potential changing from $0$ to $-1$.  Consider any node $u
  \neq v$.  If $u$ is secure, then the $u$th component of the
  potential is unchanged.  Otherwise, consider two cases.  If $v$ and
  $u$ are in different connected components, then $w(S_u(\vec{b})) =
  w(S_u(\vec{a}))$, implying that the $u$th component of the potential
  is unchanged.  If $v$ and $u$ are in the same connected component,
  then $w(S_u(\vec{b})) = w(S_v(\vec{b}))$; thus, if $u$ is happy in
  $\vec{a}$ but unhappy in $\vec{b}$, then it must be the case that
  $t_u < t_v$, implying that $u > v$.  Thus, the only components of
  the potential that can increase are the components greater than $v$,
  implying that the potential decreases lexicographically.
\end{enumerate}
Since the value of each column in the potential vector is between $-1$
and $1$, and this potential vector lexicographically decreases, we
conclude that this process converges to a pure Nash equilibrium (in
fact, in at most $3^n$ steps).
\end{proof}

Even when the security and infection costs are
uniform,~\cite{AspnesCY2006} showed that the price of anarchy is
$\Omega(n)$.  We give a more precise characterization in terms of the
vertex expansion of the contact graph.  For any graph $H$ over vertex
set $V$, the vertex expansion $\alpha(H)$ is defined as the largest
number $c$ such that for any subset $V'$ of the vertices such that
$|V'| \le |V|/2$, the set of vertices in $V \setminus V'$ that are
adjacent to a vertex in $V'$ is at least $c|V'|$. \junk{ The proof of the
following lemma is omitted due to space constraints.}
 
\begin{lemma}
\label{lemma:game.poa-dinfty}
When security and infection costs are uniform, and $w_v=1/n$ $\forall
v$, the price of anarchy in any $\GNS{\infty}$ game is
$O(1/\alpha(\CG))$.
\end{lemma}
\begin{proof}
First we calculate the lower bound for social optimum. Let $\vec{a}$ be the strategy vector of a social optimum, and $S_1, S_2,\dots, S_m$ denote the connected components in \attack. Without loss of generality, we can assume $|S_1|\le |S_2|\le \dots\le |S_m|$. We consider the following 3 cases:
\begin{enumerate}
\item $\sum_i |S_i| < n/2$, where $n$ is the total number of nodes in $\CG$. In this case more than half of the nodes are secure. Thus, social optimal cost is at least $Cn/2$.
\item $\sum_i |S_i| \ge n/2$ and $|S_m| \ge n/4$. Then social optimal cost is at least $\sum_{v\in S_m} \cost_v(\vec{a}) \ge \frac{n}{4}L\frac{n/4}{n} = Ln/16$.
\item $\sum_i |S_i| \ge n/2$ and $|S_m| < n/4$. Then there must be a $j$ such that $\sum_{i\le j} |S_i|\ge n/4$. Let $S = \cup_{i\le j} S_i$. Then the number of neighbors of set $S$ in $\CG$ is at least $\alpha(\CG)|S|\ge \alpha(\CG)n/4$. This implies social optimal cost is at least $C\alpha(\CG)n/4$.
\end{enumerate}
Therefore, the lower bound for social optimum is $\min\{Cn/2, Ln/16, C\alpha(\CG)n/4\}$.

Next we calculate the upper bound for NE cost. Let $\vec{a}$ be the strategy vector of a NE. Again, let $S_1, S_2,\dots, S_m$ denote the connected components in \attack. $|S_1|\le |S_2|\le \dots\le |S_m|$. We consider the following 2 cases.
\begin{enumerate}
\item $L\le C$. In this case no one is going to be secure in NE, which implies its cost is $nL$. The ratio between NE and the social optimum is no more than $\max\{2, 16, 4/\alpha(\CG)\}$.
\item $L > C$. The cost of NE is no more than $\sum_i L|S_i|^2 / n + Cn$. Because this is a NE, for those who choose to be insecure, $L|S_i|/2 \le C$. Therefore, we have $\sum_i L|S_i|^2 / n + Cn \le \sum_i C|S_i| + Cn \le 2Cn$. The ratio between NE and the social optimum is no more than $\max\{4, 32, 8/\alpha(\CG)\}$.
\end{enumerate}
Putting these 2 cases together completes the proof of this lemma.
\end{proof}

\subsection{The $d$-neighborhood infection model: $d > 1$}

Having established the existence of a pure NE for every instance of
the generalized network security game in both the local and the global
models, a natural question is whether pure NE exist for the entire
spectrum of $d$ in between these two extremes.  In this section, we
show that for any $1 < d < \infty$, there exist instances of $\GNS{d}$
for which there are no pure NE.  Furthermore, it is NP-complete to
determine whether a pure NE exists for a given instance.  We first
present the non-existence result which also provides the basis for the
NP-hardness reduction.

\begin{lemma}
\label{lem:no-nash}
For any fixed $d$, $1 < d < \infty$, there exists an instance of $\GNS{d}$ in which no pure NE exists.
\end{lemma}
\begin{proof}
  We first consider the case $d = 2$.  Consider the instance defined
  by the contact graph\junk{ $CN$} in Figure~\ref{fig:game.no-nash}. $w_v =
  1/n$ for all node $v$. We set the infection cost to be identical,
  say $L$, for all nodes.  For nodes D through I, we set the security
  cost to be high enough so that in any equilibrium they are all
  insecure.  That leaves nodes A, B, and C, for whom we set the
  security cost such that $9C_v/L = 7+\epsilon$ for $v$ in \{A,B,C\};
  thus, in any pure NE $\vec{a}$, node $v$ in \{A, B, C\} is secure if
  and only if $|S_v(\vec{a}[v/0])| \ge 7+\epsilon$.  We now consider
  four cases.  If all of A, B, and C are insecure in $\vec{a}$, then
  we do not have a pure NE since $|S_v(\vec{a}[v/0])| = 9$ for each
  $v$ in \{A, B, C\}.  If exactly one of A, B, or C -- say A -- is
  secure, as shown in Figure~\ref{fig:game.no-nash-a}, then B won't change
  its strategy since $|S_B(\vec{a})| = 7$, but C will change its
  strategy since $|S_C(\vec{a})| = 8$ (Notice $C$ can reach $I$, but
  $B$ cannot).  If exactly two of A, B, C -- say A and B -- are
  secure, as shown in Figure~\ref{fig:game.no-nash-ab}, then B will change
  its strategy since $|S_B(\vec{a}[B/0])| = 7$.  Finally, if all three
  are secure, then none of A, B, or C will stick to its current
  strategy since $|S_v(\vec{a}[v/0])| = 5$ for each $v$ in \{A,B,C\}.
  We have thus established that there is no pure NE in the instance of
  Figure~\ref{fig:game.no-nash}. It is easy to extend the above
  non-existence proof to larger $d$ by replacing selected edges in the
  instance of Figure~\ref{fig:game.no-nash} by multi-hop paths.
\end{proof}

\begin{figure}[htb]
\begin{center}
  \subfloat[An instance of a contact graph that has no pure
    NE.]{\label{fig:game.no-nash}\includegraphics[width=2in]{figures/no-nash.jpg}}
  \quad \subfloat[Residual graph when $A$ chooses to secure
    itself.]{\label{fig:game.no-nash-a}\includegraphics[width=2in]{figures/no-nash-a.jpg}}
  \quad \subfloat[Residual graph when $A$ and $B$ choose to secure
    themselves]{\label{fig:game.no-nash-ab}\includegraphics[width=2in]{figures/no-nash-ab.jpg}}
\caption{No pure NE example with nonuniform security costs and
  infection costs. }
\end{center}
\end{figure}

In the above non-existence proof, nodes have different security costs
and infection costs. We can extend the proof to the case of uniform
security costs and infection costs by inserting additional nodes in
the proximity of those nodes in the above instance that have lower
security costs, as shown in the following lemma.

\begin{lemma}
For any fixed $d$, $1 < d < \infty$, there exists an instance of
$\GNS{d}$ in which no pure NE exists.
\end{lemma}
\begin{proof}
We first consider the case $d = 2$. Consider the instance defined by the
contact graph in Figure~\ref{fig:game.no-nash-uniform}. $w_v = 1/n$ for all
node $v$. We set the infection cost to be $L$ and security cost to be
$C=(10+\epsilon)L/15$ for all nodes. Thus, in any pure NE $\vec{a}$,
node $v$ is secure if and only if $|S_v(\vec{a}[v/0])| \ge
10+\epsilon$. Therefore, nodes D through O are all insecure in any
pure NE. We now consider four cases. If all of A, B, and C are
insecure in $\vec{a}$, then we do not have a pure NE since
$|S_v(\vec{a}[v/0])| = 13$ for each $v$ in \{A, B, C\}. If exactly one
of A, B, or C -- say A -- is secure, as shown in
Figure~\ref{fig:game.no-nash-uniform-a}, then B won't change its strategy
since $|S_B(\vec{a})| = 10$, but C will change its strategy since
$|S_C(\vec{a})| = 11 $. If exactly two of A, B, C -- say A and B --
are secure, as shown in Figure~\ref{fig:game.no-nash-uniform-ab}, then B
will change its strategy since $|S_B(\vec{a}[B/0])| = 10$. Finally, if
all three are secure, then none of A, B, or C will stick to its
current strategy since $|S_v(\vec{a}[v/0])| = 7$ for each $v$ in \{A,
B, C\}. We have thus established that there is no pure NE in the
instance of Figure~\ref{fig:game.no-nash-uniform}. It is also easy to
extend the above non-existence proof to larger $d$ by replacing
selected edges in the  instance of Figure~\ref{fig:game.no-nash-uniform} by
multi-hop paths.
\end{proof}

\begin{figure}[htb]
\begin{center}
  \subfloat[An instance of a contact graph that has no pure
  NE.]{\label{fig:game.no-nash-uniform} \includegraphics[width=2in]{figures/no-nash-uniform.jpg}} \quad
  \subfloat[Residual graph when $A$ chooses to secure
  itself.]{\label{fig:game.no-nash-uniform-a} \includegraphics[width=2in]{figures/no-nash-uniform-a.jpg}}
  \quad 
  \subfloat[Residual graph when $A$ and $B$ choose to secure
  themselves.]{\label{fig:game.no-nash-uniform-ab} \includegraphics[width=2in]{figures/no-nash-uniform-ab.jpg}}
\caption{No pure NE example with uniform security costs and infection costs.}
\end{center}
\end{figure}

We next show that it is, in fact, NP-complete to determine whether a
given instance of the generalized network security game with $1 < d <
\infty$ has a pure NE.  It is easy to argue that the problem is in NP
since one can efficiently verify whether a given strategy vector
$\vec{a}$ is a pure NE.  In the remainder of this section, we focus on
the hardness reduction.

Our starting point is the non-existence instance defined in the
Lemma~\ref{lem:no-nash}.  We observe that if the security cost of
exactly one of the three nodes in \{G, H, I\}, say G, is reduced so
that G always secures itself, then we do have a pure NE in which C
secures itself, while A and B are insecure.  Thus, if we can control
the decision of G through an external input, then we can use the above
instance as a gadget which has the property: it has a pure NE if and
only if G is secure.  We now show how to use this gadget to obtain an
NP-hardness reduction.

\junk{
From the above section, we know that in D-neighborhood model, there
are some configurations that don't have Nash equilibrium. In this
section, we are going to show, given a configuration, telling if it
has Nash equilibrium in D-neighborhood model (non-uniform threshold)
is NP-hard.

Given the contact graph if Figure~\ref{fig:game.no-nash}, if $D$ value
is set to be 2 for everyone, which means any node within distance 2 is
defined as neighbor, $T$ (threshold) values for nodes 4 to 6 are set
to be 9, nodes 7 to 9 are set to be 6, which means they will never
vaccinate themselves, and $T$ values for node 1, 2 and 3 are set to be
7, then there is no Nash equilibrium in such configuration. But if we
can force node 7 (or 8, 9) to get vaccinated, then there is a Nash
equilibrium in this example.

\begin{lemma}
If we force node 7 to get vaccinated, then there is a Nash equilibrium in the above configuration. And the Nash equilibrium is to get node 1 vaccinated.
\end{lemma}
\begin{proof}
Since nodes 4 to 9 (except 7) are never going to vaccinate themselves, we only need to worry about node 1, 2, and 3. Because 1 and 7 are vaccinated, 2's component size is 6, and 3's component size is 7. They are both happy. For node 1, if he unvaccinates himself, he will be in a component with size 8, which is bigger than his threshold. So 1 is happy too. In sum, if we can force node 7 to get vaccinated, then having node 1 vaccinated is a Nash equilibrium.
\end{proof}


Now we have this gadget (the configuration we described above), which has Nash if we can force node 7 to get vaccine, and doesn't have Nash if we don't force any node. We are going to use this to prove telling if a configuration has a Nash equilibrium is NP-hard.
}

\begin{theorem}
The problem of determining if a $\GNS{d}$ instance, $1 < d < \infty$,
has a pure NE is NP-complete.
\end{theorem}
\begin{proof}
We reduce 3SAT problem to a $\GNS{2}$ instance, and show that a given
formula $\phi$ is satisfiable if and only if the corresponding game
has a pure NE. The reduction is shown in
Figure~\ref{fig:game.no-nash-hardness}. For each variable $X$ in the
formula, we create two nodes in the contact graph, $X$ and $\bar X$,
which are connected to each other. For each literal $l$ in the
formula, we create a node, and connect it with corresponding
variable. For each clause $C$, we create a gadget, treat node G as
clause node, and connect it to its 3 literal nodes. The costs for
gadget nodes are as before. The costs of literal nodes are set such
that their ``threshold'' -- the number of insecure nodes that can
tolerate without securing themselves -- is 1. And the threshold for
$X$ is set to be $a+1$ where $a$ is the number of adjacent literal
nodes; the threshold for $\bar X$ is set to be $b+1$ where $b$ is the
number of adjacent literal nodes.  We add padding nodes between edges
$(X,\bar X)$, $(X,I)$, $(\bar X,I)$, and $(C,I)$.  We set their
security costs to be 0, so they always wish to be secure.

We first show if $\phi$ is satisfiable, then there is a pure NE
in this game. For variable node $X$, if its
assignment is true, then make it secure. For literal node $I$, if
its assignment is false, then make it secure. If a clause is true,
then make it secure.  All the other nodes are insecure.  We now argue
that the defined strategy vector is a pure NE.  If a variable
node $X$ is secure, then all the literal nodes connected to it are not
secure, $\bar X$ is not secure, while all the literal nodes
connected to $\bar X$ are secure.  Since the formula is satisfiable,
all the clause nodes are secure.  It is clear that $\bar X$ is happy,
since its threshold is $b+1$ and $X$ is secure.  Similarly $X$ is
happy since if it were to be insecure, it will be in a component with
size $a+2$ which is bigger than its threshold. All the literal nodes
connected to $X$ are happy, because for each of them, the only two
adjacent nodes are secure. And all the literal nodes connected
to $\bar X$ are happy, because if any of them does not secure itself,
it will be in a component with size 2, which is bigger than its
threshold.  All the clause nodes are happy because the formula is
satisfiable, at least one of its literal is true, which means at least
one of its literal nodes is insecure, hence this clause node has to
secure itself because its threshold is 6. And within each gadget, we
can make node C to secure itself (together with the nodes D, E, and F)
to make all the nodes in the gadget happy.  We thus have a pure NE in
the game instance.  

Next, we argue if the game has a pure NE, then the formula is
satisfiable.  Suppose we have a pure NE strategy vector $\vec{a}$.
For each variable node $X$, if $X$ is secure, we assign $X$ to be true
for the SAT formula; and false otherwise.  We know that in any pure
NE, the clause node in each gadget has to be secure.  Furthermore,
exactly only of $X$ and $\bar{X}$ is secure.  If $X$ is secure, then
$\bar{X}$ and all the literal nodes connected to $X$ have to be
insecure, while all the literal nodes connected to $\bar X$ have to be
secure.  Since all the clause nodes are happy, at least one of its
literal nodes is not secure, implying that in each clause at least one
of the literals is true.  This establishes that the formula is
satisfiable.

In sum, the formula is satisfiable if and only if the security game
has Nash equilibrium.  It is easy to see that the above reduction can
be carried out in polynomial time, thus yielding the NP-hardness of
the problem.
\end{proof}

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=5.5in]{figures/no-nash-hardness.jpg}
\caption{\label{fig:game.no-nash-hardness} Reduction from 3SAT to $\GNS{d}$. $X_i$'s refer to variables in the boolean formula. $I_{ij}$ refers to the $j$th literal in the $i$th clause. And $C_i$'s refer to the clauses.}
\end{center}
\end{figure}
